package msb.class01;

import org.junit.Assert;
import org.junit.Test;
import common.util.ArrayUtil;

import java.util.List;

/**
 * 一个数组中有一种数出现K次，其他数都出现了M次，
 * 已知M > 1，K < M，找到出现了K次的数
 * 要求额外空间复杂度O(1)，时间复杂度O(N)
 * <p>
 * 解题思路
 * 1. 定义32位数组
 * 2. 遍历数字，将数字的二进制位的每一位对应数组的某位，并累加
 * 3. 将累加的数字进行M取余.
 * 4. 不等于0的二进制位得到的数为K数
 */
public class Code10_KM {

    public static int getK(int[] arr, int k, int m) {
        int result = 0;
        int[] sumArr = new int[32];
        for (int num : arr) {
            for (int i = 0; i < 32; i++) {
                if ((num & (-num)) == 1) {
                    sumArr[i]++;
                }
                num = num >>> 1;
            }
        }
//        System.out.println(Arrays.toString(sumArr));

        for (int i = 31; i >= 0; i--) {
            result = result << 1;
            sumArr[i] = sumArr[i] % m;
            result = result ^ (sumArr[i] / k);
        }
//        System.out.println(result);
        return result;
    }

    @Test
    public void test() {
        for (int i = 0; i < 10000; i++) {
            List<int[]> ints = ArrayUtil.instantKM();
            int[] arr = ints.get(0);
            int[] km = ints.get(1);
            int K = km[0];
            int M = km[1];
            int KNum = km[2];
            Assert.assertEquals(KNum, getK(arr, K, M));
        }
    }


}
